/**
 * @Title: HeapSort.java
 * @Package com.adamjwh.sort.heapsort
 * @Description: 
 * @author adamjwh
 * @date 2018年7月25日
 * @version V1.0
 */
package com.adamjwh.sort.heapsort;

/**
 * @ClassName: HeapSort
 * @Description: 堆排
 * @author adamjwh
 * @date 2018年7月25日
 *
 */
public class HeapSort {
	
	public static void heapSort(int[] arr) {
		for(int i=arr.length/2-1; i>=0; i--) {
			adjustHeap(arr, i, arr.length-1);
		}
		
		for(int i=arr.length-1; i>=0; i--) {
			int temp = arr[0];
			arr[0] = arr[i];
			arr[i] = temp;
			
			adjustHeap(arr, 0, i-1);
		}
	}
	
	//构造大顶堆
	public static void adjustHeap(int[] arr, int parent, int len) {
		int temp = arr[parent];
		
		for(int child=2*parent; child<len; child*=2) {
			if(child<len && arr[child] < arr[child+1]) {
				child++;
			}
			
			if(temp >= arr[child]) {
				break;
			}
			
			arr[parent] = arr[child];
			parent = child;
		}
		arr[parent] = temp;
	}
	
	//测试
	public static void main(String[] args) {
	    int[] arr = {1,9,3,12,7,8,3,4,65,22};

	    heapSort(arr);

	    for(int i:arr){
	        System.out.print(i+",");
	    }
	}

}
